UVa/11845 - Preferential Romance/11845.cpp

   1 // Accepted
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 const int MAXN = 105;
  29 bool g[MAXN][MAXN];
  30 int color[MAXN];
  31 int nodes;
  32
  33 enum { white, gray, black };
  34
  35 map<string, int> face;
  36 int currentFace;
  37
  38 int getIndex(const string &s) {
  39     if (face.count(s) > 0) return face[s];
  40     return face[s] = currentFace++;
  41 }
  42
  43 void clear() {
  44     memset(g, 0, sizeof g);
  45     face.clear();
  46     currentFace = 0;
  47 }
  48
  49 bool cycleFrom(int u) {
  50     if (color[u] == gray) return true;
  51     if (color[u] == black) return false;
  52     color[u] = gray;
  53     for (int v = 0; v < nodes; ++v) {
  54         if (!g[u][v]) continue;
  55         if (cycleFrom(v)) return true;
  56     }
  57     color[u] = black;
  58     return false;
  59 }
  60
  61 bool cycle() {
  62     for (int i = 0; i < nodes; ++i) color[i] = white;
  63     for (int i = 0; i < nodes; ++i) {
  64         if (cycleFrom(i)) return true;
  65     }
  66     return false;
  67 }
  68
  69 void solve() {
  70     if (!cycle()) {
  71         printf("F\n");
  72         return;
  73     }
  74
  75     for (int u = 0; u < nodes; ++u) {
  76         for (int v = 0; v < nodes; ++v) {
  77             if (g[u][v]) {
  78                 g[u][v] = false;
  79                 if (!cycle()) {
  80                     printf("P\n");
  81                     return;
  82                 }
  83                 g[u][v] = true;
  84             }
  85         }
  86     }
  87
  88     printf("N\n");
  89 }
  90
  91 int main(){
  92     string alice, bob;
  93     while (cin >> alice >> bob) {
  94         if (alice == "*" and bob == "*") break;
  95         string s;
  96
  97         vector< vector<string> > a(1);
  98         while (cin >> s) {
  99             if (s == ";") break;
 100             if (s == ",") {
 101                 a.push_back(vector<string>());
 102                 continue;
 103             }
 104             a.back().push_back(s);
 105         }
 106
 107         vector< vector<string> > b(1);
 108         while (cin >> s) {
 109             if (s == ";") break;
 110             if (s == ",") {
 111                 b.push_back(vector<string>());
 112                 continue;
 113             }
 114             b.back().push_back(s);
 115         }
 116
 117         clear();
 118
 119         // for (int i = 0; i < a.size(); ++i) {
 120         //     printf("row[%d] has %d items\n", i, a[i].size());
 121         //     for (int j = 0; j < a[i].size(); ++j) {
 122         //         printf("%s ", a[i][j].c_str());
 123         //     }
 124         //     puts("");
 125         // }
 126         //
 127         // for (int i = 0; i < b.size(); ++i) {
 128         //     printf("row[%d] has %d items\n", i, b[i].size());
 129         //     for (int j = 0; j < b[i].size(); ++j) {
 130         //         printf("%s ", b[i][j].c_str());
 131         //     }
 132         //     puts("");
 133         // }
 134
 135         for (int i = 0; i < a.size(); ++i) {
 136             for (int j = 1; j < a[i].size(); ++j) {
 137                 g[  getIndex(a[i][j-1])   ][  getIndex(a[i][j])  ] = true;
 138             }
 139         }
 140
 141         for (int i = 0; i < b.size(); ++i) {
 142             for (int j = 1; j < b[i].size(); ++j) {
 143                 g[  getIndex(b[i][j-1])   ][  getIndex(b[i][j])  ] = true;
 144             }
 145         }
 146
 147         nodes = currentFace;
 148         //         for (int i = 0; i < nodes; ++i) {
 149         //             for (int j = 0; j < nodes; ++j) {
 150         //                 printf("%d ", g[i][j]);
 151         //             }
 152         //             puts("");
 153         //         }
 154         //         puts("");
 155
 156         solve();
 157     }
 158     return 0;
 159 }